package com.liam.leetcode;

import java.util.ArrayList;
import java.util.List;

// https://zhuanlan.zhihu.com/p/102908327
public class 链表反转 {


    public static void main(String[] args) {
        Node headNode = init();
        printNode(headNode);
        printNode(reverse(headNode));

    }


    /**
     * p1   p2   p3
     * 1 -> 2 -> 3 -> 4 -> 5 -> null
     * 反转至少需要3个元素
     * -------------
     * 将p2 的下一个往反方向
     * p1    p2     p3
     * 1 -> <- 2    3 -> 4 -> 5 -> null
     * -------------------
     * 轮换p1  p2 p3
     *         p1    p2  p3
     * 1 -> <- 2    3 -> 4 -> 5 -> null
     * ---------------------------
     * 继续将p2指针反方向
     *         p1   p2  p3
     * 1 -> <- 2 <- 3    4 -> 5 -> null
     *-----------------
     * 最后 将第一个 的next = null
     *1 -> <- 2 <- 3 <- 4 <- 5 <- null
     *-------------------
     * null <-  1 <- 2 <- 3 <- 4 <- 5 <- nul
     *
     * @param headNode
     */
    private static Node reverse(Node headNode) {
        Node pre = headNode;
        Node curr = pre.next;
        Node next = null;
        while (curr != null){
            next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        headNode.next = null;
        headNode = pre;
        return headNode;
    }

    private static void printNode(Node headNode) {
        Node temp = headNode;
        while (temp != null){
            System.out.println(temp.value);
            temp = temp.getNext();
        }
    }

    private static Node init() {
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        Node n4 = new Node(4);
        Node n5 = new Node(5);
        n1.setNext(n2);
        n2.setNext(n3);
        n3.setNext(n4);
        n4.setNext(n5);
        return n1;
    }

    static class Node{
        public Node(int value){
            this.value = value;
        }

        private int value;
        private Node next;

        public int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }

        public Node getNext() {
            return next;
        }

        public void setNext(Node next) {
            this.next = next;
        }
    }



}
